#include <bits/stdc++.h>
using namespace std;

/*
3170. 删除星号以后字典序最小的字符串
已解答
中等
相关标签
premium lock icon
相关企业
给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。

当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：

删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。

 

示例 1：

输入：s = "aaba*"

输出："aab"

解释：

删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。

示例 2：

输入：s = "abc"

输出："abc"

解释：

字符串中没有 '*' 字符。

 

提示：

1 <= s.length <= 105
s 只含有小写英文字母和 '*' 字符。
输入保证操作可以删除所有的 '*' 字符。
*/

// 法一
// 优先队列 最小堆 谓词来排序
class Solution {
public:
    string clearStars(string s) {
        // 最小堆
        // 优先队列
        priority_queue<pair<char, int>, vector<pair<char, int>>, greater<pair<char, int>>> pq;
        vector<bool> removed(s.size(), false);

        // 迭代
        for (int i = 0; i < s.size(); i++) {
            // 负下标 以便优先队列按字典序和位置排序
            if (s[i] != '*')    pq.push({s[i], -i});
            else {
                if (!pq.empty()) {
                    auto [c, idx] = pq.top();
                    pq.pop();
                    // 弹出的就给标记 进标记数组
                    removed[-idx] = true;
                }
                // 标记 * 为已删除 
                removed[i] = true;
            }
        }
        string ans;
        for (int i = 0; i < s.size(); i++) {
            if (!removed[i])    ans += s[i];
        }
        return ans;
    }
};

// 法二
// 先排序 然后压栈 弹栈  也能完成字典序
class Solution {
public:
    string clearStars(string s) {
        // 26 个 栈 (每一个栈对应一个小写字母) 来记录每个字符的位置
        stack<int> stacks[26];
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != '*') {
                // 不是'*'  将当前字符的位置压栈
                stacks[s[i]- 'a'].push(i);
                continue;
            }

            // 是 '*' 遍历所有栈 找到第一个非空栈 --> 字典序最小的字符
            for (auto& sta : stacks) {
                if (!sta.empty()) {
                    // 给当前字符标记为 '*' 就是删除
                    s[sta.top()] = '*';
                    sta.pop();
                    break;      // 只删一个即可
                }
            }
        }
        // 删除所有标记为 * 的字符
        s.erase(ranges::remove(s, '*').begin(), s.end());
        return s;
    }
};

// 法三
// 与法二类似 最后迭代那是使用迭代器
class Solution {
public:
    string clearStars(string s) {
        // 使用26个栈（对应26个小写字母）来记录每个字符的位置
        stack<int> indexes[26];
        int sSize = s.length();
        int change = sSize; // 记录最终结果字符串的长度（初始为原字符串长度）
        
        for (int i = 0; i < sSize; i++) {
            if (s[i] != '*') {
                // 如果不是'*'，将当前字符的位置压入对应的栈
                indexes[s[i] - 'a'].push(i);
            } else {
                // 如果是'*'，需要删除左侧字典序最小的字符
                change--; // '*'本身会被删除，所以结果长度减1
                
                // 遍历26个栈（从'a'到'z'），找到第一个非空的栈
                for (int j = 0; j < 26; j++) {
                    if (!indexes[j].empty()) {
                        // 将该字符标记为'*'（相当于删除）
                        s[indexes[j].top()] = '*';
                        indexes[j].pop(); // 弹出栈顶元素
                        change--; // 被删除的字符也会减少结果长度
                        break; // 只需要删除一个字符
                    }
                }
            }
        }
        
        // 构造结果字符串（长度为change）
        string result(change, '\0');
        auto ir = result.begin(); // 结果字符串的迭代器
        
        // 遍历原字符串，跳过所有标记为'*'的字符
        for (auto it = s.begin(); it != s.end(); it++) {
            if (*it != '*') {
                *ir = *it; // 将非'*'字符复制到结果中
                ir++;
            }
        }
        return result;
    }
};